package cn.hy.考试;

/**
 *
 * 给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
 *
 * 长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
 *
 * 对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。
 *
 * 输入：head = [1,3,4,7,1,2,6]
 * 输出：[1,3,4,1,2,6]
 * 解释：
 * 上图表示给出的链表。节点的下标分别标注在每个节点的下方。
 * 由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
 * 返回结果为移除节点后的新链表。
 *
 * 输入：head = [1,2,3,4]
 * 输出：[1,2,4]
 * 解释：
 * 上图表示给出的链表。
 * 对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。
 *
 * 输入：head = [2,1]
 * 输出：[2]
 * 解释：
 * 上图表示给出的链表。
 * 对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。
 * 值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。
 *
 * 提示：
 * 链表中节点的数目在范围 [1, 10^5] 内
 * 1 <= Node.val <= 10^5
 *
 *
 */
public class Test01 {


    public static void main(String[] args) {

        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);



        Node head2 = new Node(1);
        head2.next = new Node(3);
        head2.next.next = new Node(4);
        head2.next.next.next = new Node(7);
        head2.next.next.next.next = new Node(1);
        head2.next.next.next.next.next= new Node(2);
        head2.next.next.next.next.next.next= new Node(6);


        Node head3 = new Node(2);
        head3.next = new Node(1);

        Node h = delMiddleNode(head3);

        Node cur = h;
        while (cur != null) {
            System.out.print(cur.val + "-> " );
            cur = cur.next;
        }



    }

    public static Node delMiddleNode(Node  head) {
        if (head == null) {
            return null;
        }
        if (head.next ==  null) {
            return  head;
        }

        int n = 0;
        Node cur = head;
        while (cur != null) {
            cur = cur.next;
            n ++;
        }

        int  idx = n / 2 ;

        cur = head;
        Node pre = head;
        while (idx > 0) {
           pre = cur;
           cur = cur.next;
           idx --;
        }
        pre.next = cur.next;
        return  head;
    }





    static  class Node {
        private Node next;
        private int val;

        public Node(int val) {
            this.val = val;
        }

        public Node(Node next, int val) {
            this.next = next;
            this.val = val;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    '}';
        }
    }


}
